package Midium;

import java.util.Map;

//50.Pow(x,n)
//这题一看就没思路啊，直接看答案吧
public class Solution50 {
    public double myPow(double x, int n) {
        //答案思路：分治思想，eg：x的77次方可以看做x的38次方的平方再乘以x
        //如果n为负数，则先求n的正数，最后求倒数
        //特殊情况：n == -2147483648
        if (n == -2147483648) {
            return 1/Math.pow(myPow(x, 1073741824), 2);
        }
        if (n == 0)
            return 1;
        boolean negative = false;
        if (n < 0) {
            negative = true;
            n = (-1) * n;
        }
        if (n % 2 == 0)
            return negative ? 1 / Math.pow(myPow(x, n / 2), 2) : Math.pow(myPow(x, n / 2), 2);
        else
            return negative ? 1 / (Math.pow(myPow(x, n / 2), 2) * x) : Math.pow(myPow(x, n / 2), 2) * x;
    }
}
